package com.leetcode.No0801;

import org.junit.Test;

/**
 * @program: Solution
 * @description: 使序列递增的最小交换次数
 * @author: Wang Zhihua
 * @date: 2022-10-10
 */
public class Solution {
    public int minSwap(int[] nums1, int[] nums2) {
        int len = nums1.length;
        int ans = 0;

        int curNum1 = nums1[0];
        int curNum2 = nums2[0];
        for (int i = 1; i < len; ++i) {
            // 同一数组相邻两个数的关系为 > < = 三种，一对数组相邻两个位置的关系排列组合有9种
            // 举例：数组A有 a < b，数组B有 x > y，根据题意交换后一定会有 a < y && x < b，
            // 再将四个不等式连起来，如出现矛盾则有悖题意，则这种 > < = 的组合不会出现，
            // 经过筛选总共会出现如下5种情况：
            if (curNum1 < nums1[i] && curNum2 < nums2[i]) {
                curNum1 = nums1[i];
                curNum2 = nums2[i];
            } else if ((curNum1 < nums1[i] && curNum2 > nums2[i])
                    || (curNum1 > nums1[i] && curNum2 < nums2[i])) {
                ++ans;
                curNum2 = nums1[i];
                curNum1 = nums2[i];
            } else if ((curNum1 < nums1[i] && curNum2 == nums2[i])
                    || (curNum1 == nums1[i] && curNum2 < nums2[i])) {
                ++ans;
                if (i == 1 || (nums2[i - 2] < curNum1 && nums1[i - 2] < curNum2)) {
                    curNum1 = nums1[i];
                    curNum2 = nums2[i];
                } else if (curNum1 == nums2[i - 2] || curNum2 == nums1[i - 2]) {
                    curNum2 = nums1[i];
                    curNum1 = nums2[i];
                } else { // (curNum1 != nums2[i - 2] && curNum2 != nums1[i - 2])
                    curNum1 = nums1[i];
                    curNum2 = nums2[i];
                }
            }
        }

        return Math.min(ans, len - ans);
    }

    @Test
    public void test1() {
        int[] nums1 = new int[]{1,3,5,4};
        int[] nums2 = new int[]{1,2,3,7};
        System.out.println(minSwap(nums1, nums2));

        nums1 = new int[]{0,3,5,8,9};
        nums2 = new int[]{2,1,4,6,9};
        System.out.println(minSwap(nums1, nums2));

        nums1 = new int[]{0,4,4,5, 9};
        nums2 = new int[]{0,1,6,8,10};
        System.out.println(minSwap(nums1, nums2));

        nums1 = new int[]{0,2,5,8,9,10,12,14,18,19,20,20,24,27,28,31,33,34,36,38};
        nums2 = new int[]{1,2,5,7,8, 9,11,17,15,16,19,21,28,29,30,31,33,34,38,39};
        System.out.println(minSwap(nums1, nums2));
    }
}
